package haxe.util;
import haxe.util.Stack.StackIterator;

typedef LEntry ={
	var next:LEntry;
	var prev:LEntry;
	var value:Dynamic;
}

class LinkedList<T> implements Collection<T>
{
	public static var N:Int = 6000;
	public var size(getSize,null):Int;
	public var backward(getBackwardIterator,null):Iterator<T>;
	
	private var _s:Int;
	private var _f:LEntry;
	private var _l:LEntry;
	
	public function new()
	{
		_s = 0;
	}
	
	public function add(o:T):Void
	{
		if ( _s > 0)
		{
			_l.next = {next:null, prev:_l, value:o};
			_l = _l.next;
		}
		else
		{
			_f = _l = { next:null,prev:null,value:o};
		}
		++_s;
	}
	
	public function addAll(c:Collection<T>):Void
	{
		for ( i in c )
		{
			add(i);
		}
	}
	
	public function addAfter( o:T, v:T ):Bool
	{
		var e:LEntry = _f;
		if ( o == _l.value )
		{
			add(v);
			return true;
		}
		while ( e != null && e.value != o )
		{
			e = e.next;
		}
		if ( e.value == o )
		{
			var tmp:LEntry = {prev:e,next:e.next,value:v};
			e.next.prev = tmp;
			e.next = tmp;
			++_s;
			return true;
		}else
			return false;
	}
	
	public function addBefore( o:T, v:T ):Bool
	{
		if ( o == _f.value )
		{
			addFirst(v);
			return true;
		}
		var e:LEntry = _f;
		while ( e != null && e.value != o )
		{
			e = e.next;
		}
		if ( e.value == o )
		{
			var tmp:LEntry = {prev:e.prev,next:e,value:v};
			e.prev.next = tmp;
			e.prev = tmp;
			++_s;
			return true;
		}else
			return false;
	}
	
	public function addAt(i:Int,o:T):Bool
	{
		if ( i > 0 && i < _s )
		{
			var e:LEntry = _f;
			while ( e != null && i > 0 )
			{
				e = e.next;
				--i;
			}
			if ( i == 0 )
			{
				var tmp:LEntry = {prev:e.prev,next:e,value:o};
				e.prev.next = tmp;
				e.prev = tmp;
				++_s;
				return true;
			}else
				return false;
		}
		else if ( i == 0 )
		{
			addFirst(o);
			return true;
		}
		else if ( i == _s )
		{
			add(o);
			return true;
		}else
			return false;
	}
	
	public function addLast(o:T):Void
	{
		add(o);
	}
	
	public function addFirst(o:T):Void
	{
		if ( _s > 0 )
		{
			_f.prev = {prev:null, next:_f, value:o};
			_f = _f.prev;
		}
		else
		{
			_f = _l = { next:null,prev:null,value:o};
		}
		++_s;
	}
	
	public function get( i:Int ):T
	{
		if ( i >= 0 && i < _s )
		{
			var e:LEntry = _f;
			while ( e != null && i > 0 )
			{
				e = e.next;
				--i;
			}
			if ( i == 0 )
				return e.value;
			else
				return null;
		}else
			return null;
	}
	
	public function getFirst():T
	{
		return _f.value;
	}
	
	public function getLast():T
	{
		return _l.value;
	}
	
	public function set(i:Int,o:T):Bool
	{
		if ( i >= 0 && i < _s )
		{
			var e:LEntry = _f;
			while ( e != null && i > 0 )
			{
				e = e.next;
				--i;
			}
			if ( i == 0 )
			{
				e.value = o;
				return true;
			}else
				return false;
		}else
			return false;
	}
	
	public function remove(o:T, ?equals: T->T->Bool ):Bool
	{
		if ( _f.value == o )
		{
			removeFirst();
			return true;
		}
		else if ( _l.value == o )
		{
			removeLast();
			return true;
		}
			
		var e:LEntry = _f;
		while ( e != null && e.value != o )
		{
			e = e.next;
		}
		if ( e.value == o )
		{
			e.next.prev = e.prev;
			e.prev.next = e.next;
			--_s;
			return true;
		}else
			return false;
	}
	
	public function removeAll(c:Collection<T>, ?equals: T->T->Bool ):Bool
	{
		var r:Bool = false;
		for ( i in c )
			if ( remove(i) && !r ) r = true;
		return true;
	}
	
	public function removeFirst():T
	{
		if ( _s > 0 )
		{
			var r:T = _f.value;
			_f = _f.next;
			#if neko
			if ( _s > 1 )//neko protes when null
			#end
			_f.prev = null;
			--_s;
			return r;
		}else
			return null;
	}
	
	public function removeLast():T
	{
		if ( _s > 0 )
		{
			var r:T = _l.value;
			_l = _l.prev;
			#if neko
			if ( _s > 1 )//neko protes when null
			#end
			_l.next = null;
			--_s;
			return r;
		}else
			return null;
	}
	
	public function removeAt(i:Int):T
	{
		if ( i > 0 && i < _s - 1 )
		{
			var e:LEntry = _f;
			while ( e != null && i > 0 )
			{
				e = e.next;
				--i;
			}
			if ( i == 0 )
			{
				var r:T =e.value;
				e.next.prev = e.prev;
				e.prev.next = e.next;
				--_s;
				return r;
			}else
			return null;
		}
		else if ( i == 0 )
			return removeFirst();
		else if ( i == _s - 1 )
			return removeLast();
		else
			return null;
	}
	
	public function contains( o:T, ?equals: T->T->Bool ):Bool
	{
		var i:Int = 0;
		var e:LEntry = _f;
		var n:LEntry = _l;
		while ( e != null && o != e.value && n.value != o)// maybe equals method
		{
			e = e.next;
			n = n.prev;
			++i;
		}
		return ( o == e.value || o == n.value);
	}
	
	public function containsAll(c:Collection<T>, ?equals: T->T->Bool ):Bool
	{
		for ( i in c )
		{
			if ( ! contains(i) )
				return false;
		}
		return true;
	}
	
	public function indexOf( o:T ):Int
	{
		var i:Int = 0;
		var e:LEntry = _f;
		while ( e != null && o != e.value )// maybe equals method
		{
			e = e.next;
			++i;
		}
		return if ( o == e.value ) i else -1;
	}
	
	public function lastIndexOf(o:T):Int
	{
		var i:Int = _s - 1;
		var e:LEntry = _l;
		while ( e != null && o != e.value )// maybe equals method
		{
			e = e.prev;
			--i;
		}
		return if ( o == e.value ) i else -1;
	}
	
	public function iterator():Iterator<T>
	{
		return new ListIterator( _f );//todo
	}
	
	public function listIterator():ListIterator<T>
	{
		return new ListIterator( _f );
	}
	
	private function getBackwardIterator():Iterator<T>
	{
		return new BackwardListIterator( this._f );
	}
	
	public function clear():Void
	{
		_s = 0;
		_f = _l = null;
	}
	
	public function toArray():Array<T>
	{
		return Lambda.array( this );
	}
	
	public function isEmpty():Bool
	{
		return _s == 0;
	}
	
	public function toString():String
	{
		return "LinkedList";
	}
	
	private function getSize():Int
	{
		return _s;
	}
	
	public static function main():Void
	{
		var getTime:Dynamic = 
		#if flash
			flash.Lib.getTimer;
		#else neko
			neko.Sys.time;
		#else js
			null;
		#end
		
		var list:LinkedList<Int> = new LinkedList();
		var array:Array<Int> = new Array();
		for ( i in 0...10000 )
		{
			list.add(i);
		}
		list.addAfter( 1000, 77 );
		var ind:Int = list.indexOf(77);
		trace("First index of 77 : "+ind+" check : "+list.get(ind));
		ind = list.lastIndexOf(77);
		trace("Last index of 77 : "+ind);
		list.set(ind,99);
		list.addBefore(77,99900999);
		trace("Shouild be 99900999 : "+list.get(list.indexOf(77)-1));
		list.addAfter(77,77700777);
		trace("Should be 77700777 : "+list.get(list.indexOf(77700777)));
		trace("Index of 50000 : "+list.indexOf(50000));
		trace("Size : "+list.size);
		list.clear();
		
		var t:Int = getTime();
		for( i in 0...N )
		{
			list.add(i);
		}
		trace("LinkedList adding on top time : "+( getTime() -t));
		
		t = getTime();
		for( i in 0...N )
		{
			array.push(i);
		}
		trace("Array adding on top time : "+( getTime() -t));
		
		array = new Array();
		list.clear();
		
		t = getTime();
		for( i in 0...N )
		{
			list.addFirst(i);
		}
		trace("LinkedList adding on bottom time : "+( getTime() -t));
		
		t = getTime();
		for( i in 0...N )
		{
			array.unshift(i);
		}
		trace("Array adding on bottom time : "+( getTime() -t));
		
		trace("LinkedList.size : "+list.size);
		var success:Bool = true;
		t = getTime();
		for( i in 0...100 )
		{
			success = list.addAt( 100, i);
		}
		trace("LinkedList - 100 inserts in the middle : "+( getTime() -t));
		trace("LinkedList.size : "+list.size);
		trace("success : "+success);
		
		t = getTime();
		for( i in 0...100 )
		{
			array.insert( Math.round(array.length/2), i );
		}
		trace("Array - 100 inserts in the middle : "+( getTime() -t));
		trace("Array.length : "+array.length );
		trace("LinkedList.length : "+list.size );
	}
}
class ListIterator<T>
{
	//private var _f:LEntry;
	//private var _l:LEntry;
	private var _e:LEntry;
	
	public function new( f:LEntry )
	{
		_e = {next:f,prev:null,value:null};
	}
	
	public function hasNext():Bool
	{
		return _e.next != null;
	}
	
	public function hasPrev():Bool
	{
		return _e.prev != null;
	}
	
	public function next():T
	{
		var r:T = _e.value;
		_e = _e.next;
		return r;
	}
	
	public function prev():T
	{
		var r:T = _e.value;
		_e = _e.prev;
		return r;
	}
	
	/*public function remove():T
	{
		_e.next.prev = _e.prev;
		_e.prev.next = _e.next;
		return _e.value;
	}*/
	
	public function toString():String
	{
		return "ListIterator";
	}
}
class BackwardListIterator<T>
{
	//private var _f:LEntry;
	//private var _l:LEntry;
	private var _e:LEntry;
	
	public function new( f:LEntry )
	{
		_e = {next:null,prev:f,value:null};
	}
	
	public function hasNext():Bool
	{
		return _e.prev != null;
	}
	
	public function next():T
	{
		_e = _e.prev;
		return _e.value;
	}
	
	public function toString():String
	{
		return "BackwardListIterator";
	}
}
class StrongListIterator<T> extends ListIterator<T>
{
	private function set(o:T):Void
	{
		_e.value = o;
	}
	
	public function toString():String
	{
		return "StrongListIterator";
	}
}